package Leetcode第一期;

public class n个骰子的点数_1604 {

    //找规律：s共有 6^n种情况，共有5*n+1种不重复结果
    public double[] twoSum(int n) {
        //思路一：遍历 5*n+1种不重复结果，计算每一种不重复结果的组合个数
        double[] res = new double[5 * n + 1];
        int curSum = n;
        for (int i = 0; i < res.length; i++) {
            //最小值n开始 curSum=n
            res[i] = countSum(curSum, n) / Math.pow(6, n);
            ++curSum; //比如三个骰子，就从3开始加到18
        }
        return res;
    }

    int countSum(int curSum, int n) {
        if (n < 0 || curSum < 0) return 0;
        if (n == 0 && curSum == 0) return 1;
        int sum = 0;
        for (int i = 1; i < 7; i++) {
            //一共1到6个数字
            sum += countSum(curSum - i, n - 1);
        }
        return sum;
    }

    public double[] twoSum2(int n) {
        //二维数组进行运算 dp[n][j]=dp[n-1][j-i] (i属于[1,6])
        int[][] dp=new int[n][6*n];
        //初始化
        for(int j=0;j<6;j++){dp[0][j]=1;}
        for(int i=1;i<n;i++){
            for(int j=i;j<(i+1)*6;j++){
                for(int disc=1;disc<7;disc++){
                    if(j-disc<0){break;}
                    dp[i][j]+=dp[i-1][j-disc]; //假如两枚骰子，第j个数，范围在2到12，为第一枚骰子的j减去1到6出现的次数之和。
                }
            }
        }
        double[] res=new double[5*n+1];//无重复出现的概率
        int j=n-1;
        for(int i=0;i<res.length;i++){
            res[i]=dp[n-1][j++]/Math.pow(6,n);
        }
        return res;

    }

}
